import java.sql.ClientInfoStatus;
import java.util.ArrayList;
import java.util.List;

class Solution1 {
    List<String> list = new ArrayList<>();
    StringBuffer str = new StringBuffer();

    public List<String> letterCasePermutation(String s) {

        dfs(s, 0);
        return list;
    }

    public void dfs(String s, int u) {
        if (u == s.length()) {
            list.add(new String(str));
            System.out.println(str);
            return;
        }
        char ch = s.charAt(u);
        if (!isAlpha(ch)) {
            str.append(ch);
            dfs(s, u + 1);
            str.deleteCharAt(str.length() - 1);
        } else {
            str.append(ch);
            dfs(s, u + 1);
            str.deleteCharAt(str.length() - 1);

            if (ch >= 'a' && ch <= 'z') {
                ch += 'A' - 'a';
            } else {
                ch -= 'A' - 'a';
            }
            str.append(ch);
            dfs(s, u + 1);
            str.deleteCharAt(str.length() - 1);
        }
    }

    public boolean isAlpha(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }
}

class Solution2 {
    int count = 0;
    boolean[] st;
    List<Integer> list = new ArrayList<>();

    public int countArrangement(int n) {
        st = new boolean[n + 1];
        dfs(1, n);
        return count;
    }

    public void dfs(int u, int n) {
        if (u == n + 1) {
            count++;
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!st[i]) {
                if (i % u == 0 || u % i == 0) {
                    st[i] = true;
                    list.add(i);
                    dfs(u + 1, n);
                    st[i] = false;
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}

class Solution3 {
    List<List<String>> lists = new ArrayList<>();
    List<String> list = new ArrayList<>();
    int n;
    boolean[] row; //行
    boolean[] col; //列
    boolean[] dig1; //主对角线
    boolean[] dig2; //副对角线
    StringBuffer str = new StringBuffer();

    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        row = new boolean[n];
        col = new boolean[n];
        dig1 = new boolean[n * 2];
        dig2 = new boolean[n * 2];
        dfs(0);
        return lists;
    }

    public void dfs(int u) {
        if (u == n) {
            lists.add(list);
            return;
        }
        for (int i = 0; i < n; i++) {
            //放
            if (check(u, i)) {
                row[u] = true;
                col[u] = true;
                dig1[i-u+n] = true;
                dig1[i+u] = true;
                str.append('Q');
                dfs(u+1);
                row[u] = false;
                col[u] = false;
                dig1[i-u+n] = false;
                dig2[i+u] = false;
                if(str.length() == n) {
                    list.add(new String(str));
                }
                str.deleteCharAt(str.length()-1);
            }
            //不放
            str.append('.');
            dfs(u+1);
            if(str.length() == n) {
                list.add(new String(str));
            }
            str.deleteCharAt(str.length()-1);
        }

    }

    public boolean check(int x, int y) {
        if (row[x] || col[y]) return false;
        if (dig1[y-x+n] || dig2[y+x]) return false;
        return true;
    }
}

public class Test {
    public static void main(String[] args) {
        int ret = new Solution2().countArrangement(2);
    }

    public static void main1(String[] args) {
        char ch = 'a';
        ch += 'A' - 'a';
        System.out.println(ch);
        List<String> ret = new Solution1().letterCasePermutation("3z4");
    }
}
